#include<stdio.h>

void Swap(int* left, int* right) {
	int temp = *left;
	*left = *right;
	*right = temp;
	return;
}

//交换排序-》快速排序(升序)

//基准值优化方式：三数取中法(返回下标）
int GetMiddleIndex(int* arr, int left, int right) {
	int mid = left + ((right - left) >> 1);
	if (arr[left] > arr[right - 1]) {
		if (arr[mid] < arr[right - 1])
			return right - 1;
		else if (arr[mid] > arr[left])
			return left;
		else
			return mid;
	}
	else {
		if (arr[left] > arr[mid])
			return left;
		else if (arr[mid] > arr[right - 1])
			return right - 1;
		else
			return mid;
	}
}

//前后指针
int Partion3(int* arr, int left, int right) {
	int cur = left;
	int prev = cur - 1;
	int mid = GetMiddleIndex(arr, left, right);
	if (mid != right - 1)
		Swap(&arr[mid], &arr[right - 1]);
	int key = arr[right - 1];
	while (cur < right - 1) {
		if (arr[cur] < key && ++prev != cur)
			Swap(&arr[cur], &arr[prev]);
		cur++;
	}
	if (++prev != right - 1)
		Swap(&arr[prev], &arr[right - 1]);
	return prev;
}
//挖坑法
int Partion2(int* arr, int left, int right) {
	int begin = 0;
	int end = right - 1;
	int mid = GetMiddleIndex(arr, left, right);
	if (mid != end)
		Swap(&arr[mid], &arr[end]);
	int key = arr[end];	
	while (begin < end) {
		while (begin < end && arr[begin] <= key)
			begin++;
		if(begin < end){
			arr[end] = arr[begin];
			end--;
		}
		while (begin < end && arr[end] >= key)
			end--;
		if (begin < end) {
			arr[begin] = arr[end];
			begin++;
		}
	}
	if (begin != right - 1)
		arr[begin] = key;//这里注意是key而不能像Hoare一样写arr[right - 1],因为挖坑法中，arr[right - 1]已经被占用
	return begin;
}
//Hoare 法
int Partion1(int* arr, int left, int right) {
	int begin = left;
	int end = right - 1;
	int mid = GetMiddleIndex(arr, left, right);
	if (mid != end)
		Swap(&arr[mid], &arr[end]);
	int key = arr[end];
	while (begin < end) {
		while (begin < end && arr[begin] <= key)
			begin++;
		while (begin < end && arr[end] >= key)
			end--;
		if (begin != end)
			Swap(&arr[begin], &arr[end]);
	}
	if (right - 1 != begin)
		Swap(&arr[begin], &arr[right - 1]);
	return begin;
}
//最坏情况下，递归深度类似单支树-》n，因此时间复杂度为O（n^2）,因此对于基准值的取值优化需要注意
//时间复杂度：递归深度 * 每层比较次数：logN * n
//空间复杂度：递归深度（栈的深度）：log(N)
//适用环境：数据量大且杂乱

void InsertSort(int* arr, int size) {
	for (int i = 1; i < size; i++) {
		int end = i - 1;
		int key = arr[i];
		while (end >= 0 && arr[end] > key) {
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = key;
	}
	return;
}

void QuickSort(int* arr, int left, int right) {
	//if (right - left <= 1)
	//	return;

	//防止递归过深导致栈溢出，结合直接插入排序使用
	if (right - left <= 16) {
		InsertSort(arr + left, right - left);
		return;
	}
	//int div = Partion1(arr, left, right);
	//int div = Partion2(arr, left, right);
	int div = Partion3(arr, left, right);
	QuickSort(arr, left, div);
	QuickSort(arr, div + 1, right);
	return;
}

void SortPrint(int* arr, int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

int main() {
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	int size = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, size);//[left,right)，下标，左闭右开
	SortPrint(arr, size);
	return 0;
}
//#endif 
